|
In graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections). This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures. Most of these methods operate in O(''n'') time (linear time), where ''n'' is the number of edges (or vertices) in the graph, which is asymptotically optimal. Rather than just being a single Boolean value, the output of a planarity testing algorithm may be a planar graph embedding, if the graph is planar, or an obstacle to planarity such as a Kuratowski subgraph if it is not. ==Planarity criteria== Planarity testing algorithms typically take advantage of theorems in graph theory that characterize the set of planar graphs in terms that are independent of graph drawings. These include *Kuratowski's theorem that a graph is planar if and only if it does not contain a subgraph that is a subdivision of ''K''5 (the complete graph on five vertices) or ''K''3,3 (the utility graph, a complete bipartite graph on six vertices, three of which connect to each of the other three). *Wagner's theorem that a graph is planar if and only if it does not contain a minor (subgraph of a contraction) that is isomorphic to ''K''5 or ''K''3,3. *The Fraysseix–Rosenstiehl planarity criterion, characterizing planar graphs in terms of a left-right ordering of the edges in a depth-first search tree. The Fraysseix–Rosenstiehl planarity criterion can be used directly as part of algorithms for planarity testing, while Kuratowski's and Wagner's theorems have indirect applications: if an algorithm can find a copy of ''K''5 or ''K''3,3 within a given graph, it can be sure that the input graph is not planar and return without additional computation. Other planarity criteria, that characterize planar graphs mathematically but are less central to planarity testing algorithms, include Whitney's planarity criterion that a graph is planar if and only if its graphic matroid is also cographic, Mac Lane's planarity criterion characterizing planar graphs by the bases of their cycle spaces, Schnyder's theorem characterizing planar graphs by the order dimension of an associated partial order, and Colin de Verdière's planarity criterion using spectral graph theory. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Planarity testing」の詳細全文を読む スポンサード リンク
|